package leetcode

import kotlinetc.println

//https://leetcode.com/problems/search-in-rotated-sorted-array/
/**
Suppose an sort.getArray sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the sort.getArray return its index, otherwise return -1.

You may assume no duplicate exists in the sort.getArray.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
 */
fun main(args: Array<String>) {

    //[4,5,6,7,0,1,2]
    //0
    search(intArrayOf(4, 5, 6, 7, 0, 1, 2), 0).println()
    //                0, 1, 2, 3, 4, 5, 6
}

/**
 * 這題的思路在于并不知道旋转到哪个位置，但是肯定的一点是，不管怎样旋转，总有一边的排序是连续的
 * 可以先确定连续的那边是否包含目标，不然就在另一边
 */
fun search(nums: IntArray, target: Int): Int {

    if (nums.isEmpty()) return -1

    var result = -1

    var l = 0
    var r = nums.size - 1
    var mid = (l + r + 1) / 2
    while (l <= r) {
        val m = nums[mid]
        if (m == target) {
            result = mid
            break
        }
        //如果左边连续，并且落在左边范围
        if (nums[l] <= m) {
            if (target >= nums[l] && target <= m)
                r = mid - 1
            else l = mid + 1

        } else if (nums[r] >= m) {
            if (target >= m && target <= nums[r])
                l = mid + 1
            else r = mid - 1
        }
        mid = (l + r + 1) / 2
    }

    return result
}